﻿#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
struct treeNode
{
	int a;
	struct treeNode* left;
	struct treeNode* right;
	struct treeNode* Dad;
};
struct stack//双向链表栈(尾添加尾删除)
{
	struct stack* pre;
	struct treeNode* node;
	struct stack* next;
};
struct stack head;
struct stack* stacktop = &head;
void push(struct treeNode* root)//入栈
{
	if (root == NULL)
		return;
	//申请节点
	struct stack* tp = (struct stack*)malloc(sizeof(struct stack));
	//节点赋值
	if (tp == NULL)
		return;
	tp->pre = NULL;
	tp->next = NULL;
	tp->node = root;
	//节点链接
	stacktop->next = tp;
	tp->pre = stacktop;
	stacktop = tp;
}
struct treeNode* pop()//出栈
{
	if (stacktop == &head)
		return NULL;
	struct treeNode* tp = stacktop->node;
	stacktop = stacktop->pre;
	free(stacktop->next);//这里是在栈里释放
	stacktop->next = NULL;
	return tp;
}
void freetree(struct treeNode** root)//树中释放
{
	struct treeNode* t = *root;
	while (1)
	{
		while (t!= NULL)
		{
			push(t);
			t=t->left;
		}
		if (stacktop == &head)
			return;
		t = pop();//出栈
		struct treeNode* tp = t;//记录变化前
		t = t->right;//用于前序遍历
		free(tp);//用完再释放
	}
	*root = NULL;//树清空记得根要赋值为空
}
struct treeNode* FindtreeNode(struct treeNode* root,int data)//二叉排序树 查找节点 
{
	while (root != NULL)
	{
		if (root->a == data)
			return root;
		if (root->a > data)
			root = root->left;
		else
			root = root->right;
	}
	return NULL;
}
int count_1(struct treeNode* root, int data)//统计重复数据
{
	int n = 0;
	while (root != NULL)//if else—if else三者互斥
	{
		if (data == root->a)//第一个if和以下不互斥 相等一次记一次
			n++;
		if (data > root->a)
			root = root->right;
		else//有一个等于
			root = root->left;
	}
	return n;
}
int count_2(struct treeNode* root, int data)
{
	int i = 0;
	struct treeNode* tp = FindtreeNode(root, 2);//先找到第一个相等的数据
	while (1)
	{
		if (tp == NULL)//没有找到 树里面没这个节点
			break;
		else
		{
			i++;
			tp = FindtreeNode(tp->left, 2);//相等的数据一定在左边 没有找到即tp为NULL
		}
	}
	return i;
}
bool delete(struct treeNode** root, int data)//删树内的节点
{
	void DeleteRoot(struct treeNode** root);
	void DeleteMid(struct treeNode** root);
	if (*root == NULL)//空树
		return false;
	//找到它——删除它
	struct treeNode* node = FindtreeNode(*root, data);
	if (node == NULL)
		return false;
	//删除节点是根
	if (node == *root)
	{
		DeleteRoot(root);
	}
	//删除节点是叶子
	else if (node->left == NULL && node->right == NULL)
	{
		if (node == node->Dad->left)//左叶子
			node->Dad->left = NULL;
		else if (node == node->Dad->right)//右叶子
			node->Dad->right = NULL;
		free(node);
	}
	//删除节点是中间节点
	else
	{
		DeleteMid(&node);
	}
	return true;
}
void DeleteMid(struct treeNode** root)
{
	struct treeNode* node = *root;
	//左子树有 右子树没有 左子树替换删除节点
	if (node->left != NULL && node->right == NULL)
	{
		if (node = node->Dad->left)
			node->Dad->left = node->left;
		else
			node->Dad->right = node->left;	
		node->left->Dad = node->Dad;
		free(node);
	}
	//右子树有 左子树没有 右子树替换删除节点
	else if (node->left == NULL && node->right != NULL)
	{
		if (node = node->Dad->right)
			node->Dad->right = node->right;
		else
			node->Dad->left= node->right;
		node->right->Dad = node->Dad;
		free(node);
	}
	//左右都有子树
	else
	{
		struct treeNode* top = (*root)->left;
		while (top->right != NULL)
			top = top->right;
		//链接
		top->right = node->right;
		node->right->Dad = top;
		if (node = node->Dad->left)
			node->Dad->left = node->left;
		else
			node->Dad->right = node->left;
		node->left->Dad = node->Dad;
		free(node);
	}
}
void Change(struct treeNode** root, int data,int Value)//修改指定数据
{
	bool delete(struct treeNode** root, int data);
	void insert(struct treeNode** root, int data);
	bool nres = true;
	while (1)
	{//删->修改->添加
		nres = delete(root, data);
		if (nres == false)//可能多个
			break;
		insert(root, Value);
	}
}
void Remove(struct treeNode** root, int data)//去重
{
	int n = count_1(root, data);//重复才去重
	if (n <= 1)
		return;
	void insert(struct treeNode** root, int data);
	bool nes = true;
	while (nes)
	{
		nes=delete(root, data);
	}
	insert(root, data);
}
void DeleteRoot(struct treeNode**root)
{
	struct treeNode* node = *root;//要的是里面的内容 代替根指针去遍历
	{//删除节点是树根
		if (node->left == NULL && node->right == NULL)
		{//仅有树根
			free(node);
			*root = NULL;
		}
		else if (node->left != NULL && node->right == NULL)
		{//仅一面
			*root = node->left;//变新根
			(*root)->Dad = NULL;
			free(node);//释放老根
		}
		else
		{//都有（维持左小右大）1.右子树连左子树最右端节点 2.左子树连接在右子树最左端节点
			struct treeNode* tp = node->left;
			while (tp->right != NULL)
			{
				tp = tp->right;
			}
			tp->right = node->right;
			node->right->Dad = tp;
			//换根 释放旧根
			*root = node->left;
			tp->Dad = NULL;
			free(node);
		}
	}
}
void insert(struct treeNode** root, int data)//树上添节点
{//二级指针：改变树本身结构

	//创建节点
	struct treeNode* tp = (struct treeNode*)malloc(sizeof(struct treeNode));
	//节点赋值
	if (tp == NULL)
		return;
	tp->left = NULL;
	tp->right = NULL;
	tp->Dad = NULL;
	tp->a = data;
	//链接节点
	if (NULL == *root)//如果树为空 节点即树根
		*root = tp;
	else
	{//找位置--再连接（升序）
		struct treeNode* temp = *root;
		struct treeNode**jilu = NULL;
		struct treeNode* te = NULL;
		while (temp != NULL)
		{ 
			te = temp;
			//jilu = temp;
			if (temp->a < data)
			{
				jilu = &temp->right;//记录temp的左右指针的地址
				temp = temp->right;
			}
			else if(temp->a >= data)
			{
				jilu = &temp->left;
				temp = temp->left;
			}
		}
		*jilu = tp;//直接连接 记录成员地址
		tp->Dad = te;
		////链接  jilu记录的是父节点 左or右子树
		//if (jilu->a < data) {
		//	jilu->right = tp;
		//}
		//else {
		//	jilu->left = tp;
		//}
		//tp->Dad = jilu;
	}
}
void look(struct treeNode* root)//遍历树 前序遍历递归写法
{
	if (root !=NULL)
	{
		printf("%d", root->a);
		look(root->left);
		look(root->right);
	}
}
void CreatTree(struct treeNode** root,int* arr, int len)//创建树
{
	for (int i = 0; i < len; i++)
		insert(root, arr[i]);
}
int main()
{
	struct treeNode* root = NULL;
	int arr[10] = { 10,5,15,2,7,1,3,5,8};//查找节点 统计重复数据跟树本身有关 即据树本身设计函数
	CreatTree(&root,arr,9);
	look(root);
	printf("\n");
	//Remove(&root, 5);
	Change(&root, 5,20);
	look(root);
	/*int a = count_2(root, 2);
	printf("%d",a);
	struct treeNode* pp = FindtreeNode(root, 3);
	printf("%d",pp->a);
	freetree(&root);*/
	return 0;
}
